package greedy;

import java.util.Arrays;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/27 17:22
 * https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
 */
public class LargestSumAfterKNegations {

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int index = 0;
        int sum = 0;
        //翻转k次
        for (int i = 0; i < k; i++) {
            if (i < nums.length - 1 && nums[i] < 0) {
                nums[index] = -nums[index];
                if (nums[index] >= Math.abs(nums[index + 1])) {
                    index++;
                }
                continue;
            }
            //剩余正数，nums[index]为最小正数
            nums[index] = -nums[index];
        }
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }

    public static void main(String[] args) {

    }
}
